package summary;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/22 15:01
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class Title300 {

    /**
     * dp[i]表示i位置前（包括i）的以nums[i]结尾的最大子序列长度 （不一定最后一个最大）
     * 递推公式：if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1)
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if(dp[i] > max){
                max = dp[i];
            }
        }
        return max;
    }



    public int lengthOfLIS2(int[] nums) {
        //dp[i]表示下标为i的节点时，最长递增子序列数组的长度
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }









    public static void main(String[] args) {

    }
}
